1. Field of the Invention
The present invention relates generally to methods and apparatuses for construction of codes for data-compression. More specifically, the present invention describes a method for constructing efficient Slepian-Wolf codes for providing improved data compression for video coding systems based on Wyner-Ziv principles.
2. Background Description
Slepian-Wolf codes refer to codes used for compressing source data at an encoder, in the scenario where the decoder has access to side-information not available at the encoder. These are of great interest in several applications, including important applications in multimedia data compression. Examples of such applications include, but are not limited to, low complexity encoding of media, distributed source coding for sensor networks, scalable video coding etc. Video compression systems employing Slepian-Wolf codes are termed Wyner-Ziv video compression systems.
FIG. 1 shows a generic Wyner-Ziv video compression system. In general, a Wyner-Ziv video compression system includes a video encoder which compresses (or encodes) a video signal, and a video decoder which decompresses (or decodes) the video signal. At a given time-instant t, the video frame ft 105 is to be encoded by the encoder. In order to decode the video frame ft, the decoder employs the frame decoded at the previous time-instant ft-1 185. The knowledge that this previously reconstructed video-frame will be used during decompression, allows the encoder to transmit fewer bits, and thus achieve greater compression, than would otherwise be possible.
This is achieved as follows. The encoder first compresses ft 105 conventionally, using an energy-compacting transform 110 and quantization 120 (equivalent to the intra mode transform and quantization in MPEG coding). The resultant signal X 125, termed the Slepian-Wolf source, is then further compressed 130 by using a Slepian-Wolf code 145 generated by a code construction function 140. The output of compression 130 is a set of symbols 135 termed syndromes. These syndromes represent the compressed video signal. The decoder derives a signal Y 195, termed the Slepian-Wolf side-information, which is used to decode 150 the signal X 155 from the syndromes 135. Then the decoded signal X 155 is subjected to an inverse quantization 160 and inverse energy compacting transform 170 to obtain the reconstructed frame ft 175.
Both Y 195 and X 155 take values in discrete sets; denote these sets as  and  respectively. The efficiency of compression (measured by the bit-rate of the syndromes 135 required to decode X 125 successfully at 155) depends, among other factors, on the joint probability distribution of X 125 and Y 195, given by the marginal distribution of X {Px(i)}iε and the conditional distribution of Y {pY|X=i(j|i)} iε,yε, and on the goodness of the Slepian-Wolf code employed. The better the Slepian-Wolf code, the lower is the number of syndrome bits 135 required for successful decoding, for a given joint distribution. Slepian-Wolf codes that come close to the theoretical compression limit are termed good Slepian-Wolf codes.
Previous methods for constructing Slepian Wolf codes, have been described by Pradhan and Ramchandran, Distributed source coding using syndromes (DISCUS): design and construction, IEEE Transactions on Information Theory, March 2003, J. Garcia-Frias and Y. Zhao, Compression of correlated binary sources using turbo codes, IEEE Communications Letters, 5:417–419, October 2001, and V. Stankovic et al., On code design for the general Slepian-Wolf problem and for lossless multiterminal communication networks, IEEE Transactions on Information Theory, April 2006, J. Bajcsy and P. Mitran, Coding for the Slepian-Wolf problem with turbo codes, IEEE GLOBECOM, pp. 1400–1404, November 2001, A. Aaron and B. Girod, Compression with side information using turbo codes, Proceeding of IEEE Data Compression Conference (DCC), pp. 252–261, April 2002, A. D. Liveris et al., Compression of binary sources with side information at the decoder using LDPC codes, IEEE Communications Letters, vol. 6, pp. 440–442, 2002, T. Richardson, A. Shokrollahi, and R. Urbanke, Design of capacity-approaching irregular low-density parity-check codes, IEEE Trans. Inform. Theory, vol. 47, pp. 619–637, February 2001. These methods are restricted to the case where the conditional distribution {pY|X=i(j/i)} iε,yε, termed the channel between the source and the side-information, is output symmetric with respect to X, and these methods use linear codes designed for this output symmetric channel as Slepian-Wolf codes.
The motivation for doing this is that the design of good channel codes for output symmetric channels is well-known. In particular, the method of density evolution can be used to design efficient codes for such channels, which approaches the theoretical channel capacity.
The chief drawback of these methods is that, since they do not deal with the complete joint distribution but merely the conditional distribution p(•|•), the constructed codes can be very inefficient for Slepian-Wolf coding. For example, as has been previously reported in Li et al., Slepian-Wolf coding for nonuniform sources using Turbo codes, Proceeding of IEEE Data Compression Conference (DCC), pp. 312–321, March 2004, if the input source does not have a uniform probability distribution, these codes can be arbitrarily inferior, compared to the best theoretically achievable Slepian-Wolf performance. Similarly if the actual correlation channel is not output symmetric, these constructions yield codes with poor Slepian-Wolf performance.
FIG. 2 shows the conventional Slepian-Wolf code design methodology. As can be seen the conditional distribution channel p(•|•) 220 is input to the density evolution method 230, and the resultant channel code 245 is used as a Slepian-Wolf code. Note that joint distribution 210 is not taken into account in developing the Slepian-Wolf code 245.
To eliminate the performance loss in Wyner-Ziv coding, caused by inefficient Slepian-Wolf codes, it is essential that the joint distribution 210 be taken into account when designing the Slepian-Wolf code. The main hurdle faced in this attempt is that there are no previously known computationally feasible methods for constructing good Slepian-Wolf codes for arbitrary distributions.